\documentclass{sciposter}


\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multicol}
%\usepackage{fancybullets}

\newtheorem{Def}{Definition}

%\definecolor{BoxCol}{rgb}{0.9,0.9,0.9}
% uncomment for grey background to \section boxes 
% for use with default option boxedsections

%\definecolor{BoxCol}{rgb}{0.9,0.9,1}
% uncomment for light blue background to \section boxes 
% for use with default option boxedsections

%\definecolor{SectionCol}{rgb}{0,0,0.5}
% uncomment for dark blue \section text 






\title{Generalized Pattern Spectra Sensitive to Spatial Information}

% Note: only give author names, not institute
\author{Michael H. F. Wilkinson}
 
% insert correct institute name
\institute{Institute for Mathematics and Computing Science,\\
           University of Groningen\\}

\email{michael@cs.rug.nl}  % shows author email address below institute

%\date is unused by the current \maketitle


% The following commands can be used to alter the default logo settings
%\leftlogo[0.9]{logoWenI}{  % defines logo to left of title (with scale factor)
%\rightlogo[0.52]{RuGlogo}  % same but on right

% NOTE: This will require presence of files logoWenI.eps and RuGlogo.eps, 
% or other supported format in the current directory  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Begin of Document



\begin{document}
%define conference poster is presented at (appears as footer)

\conference{{\bf ICPR 2002}, 16th International Conference on Pattern
  Recognition, 11-15 August 2002, Qu\'ebec City, Canada}

%\LEFTSIDEfootlogo  
% Uncomment to put footer logo on left side, and 
% conference name on right side of footer

% Some examples of caption control (remove % to check result)

%\renewcommand{\algorithmname}{Algoritme} % for Dutch

%\renewcommand{\mastercapstartstyle}[1]{\textit{\textbf{#1}}}
%\renewcommand{\algcapstartstyle}[1]{\textsc{\textbf{#1}}}
%\renewcommand{\algcapbodystyle}{\bfseries}
%\renewcommand{\thealgorithm}{\Roman{algorithm}}

\maketitle

%%% Begin of Multicols-Enviroment
\begin{multicols}{3}

%%% Abstract
\begin{abstract}
Morphological pattern spectra computed from granulometries are frequently used
to classify the size classes of details in textures and images. An extension 
of this technique, which retains information on the spatial 
distribution of the details in each size class is developed. Algorithms for
computation of these spatial pattern spectra for a large number of 
granulometries on binary images are presented. 
\end{abstract}

%%% Introduction
\section{Introduction}

\PARstart{G}{ranulometries} are ordered sets of morphological openings or closings, each of
which removes image details below a certain size. These can be used for texture
analysis
through the use of \emph{pattern spectra}, which show how the number of 
foreground pixels in the image changes as a function of the size parameter 
\cite{maragos89:_patter}.
A drawback of the classical definition of pattern spectra is that spatial 
information is not included in a pattern spectrum as shown below.
 In this paper, \emph{spatial pattern spectra} are developed which retain information on the distribution of these details at different scales.
 

\newcommand{\imsize}{0.45\columnwidth}
\begin{figure}
\begin{center}
\begin{tabular}{c c}
{\resizebox{\imsize}{!}{\includegraphics{blocks1}}} &
{\resizebox{\imsize}{!}{\includegraphics{blocks2}}}\\
(a) & (b) \\
{\resizebox{\imsize}{!}{\includegraphics{blocks3}}} &
{\resizebox{\imsize}{!}{\includegraphics{blocks1a}}}\\
(c) & (d) \\
\end{tabular}
\end{center}
\caption{ Parts (a) through (c) show three images consisting of squares of
different sizes;
(d) shows the pattern spectra, denoting the number of foreground pixels 
 removed by openings by reconstruction by $\lambda \times \lambda$ squares. No 
granulometry is capable of separating the patterns, because the only 
differences between the images lie in the distributions of the 
connected components. }\label{fig:blocks}
\end{figure}




\section{Theory}

Let binary images $X$ and $Y$ be defined as a subset of the image domain 
${\mathbf M}\subset {\mathbb Z}^n$ or ${\mathbb R}^n$ (usually $n=2$). 
\begin{Def}
A binary 
granulometry is a set of operators $\{\alpha_r\}$ with $r$ from some ordered 
set $\Lambda$ (usually $\Lambda \subset {\mathbb R}$ or ${\mathbb Z}$), with 
the following three properties
\begin{align}
   \alpha_r(X) & \subset  X \label{eq:antiext} \\
   X \subset Y & \Rightarrow \alpha_r(X) \subset \alpha_r(Y) 
   \label{eq:increasing} \\
   \alpha_r(\alpha_s(X)) & =  \alpha_{\max(r,s)}(X) \label{eq:idempot},
\end{align}   
for all $r,s \in \Lambda$.
\end{Def}

\begin{Def}
The pattern spectrum $s_{\alpha}(X)$ obtained by applying 
granulometry $\{\alpha_r\}$ to a binary image $X$ is defined as
\begin{equation}
    (s_{\alpha}(X))(u) = 
    - \frac{\partial A(\alpha_r(X))}{\partial r}\bigg{\vert}_{r=u}
\end{equation}
in which $A(X)$ is a function denoting the Lebesgue measure in 
${\mathbb R}^n$.
\end{Def} 
In the case of discrete images, and with $r \in \Lambda \subset {\mathbb Z}$, 
this differentiation reduces to
\begin{align}
    (s_{\alpha}(X))(r)  & = \#(\alpha_{r}(X) \setminus \alpha_{r^+}(X)) \\ 
                        & = \#(\alpha_{r}(X)) - \#(\alpha_{r^+}(X)), 
\end{align}
with $r^+ = \min\{ r' \in \Lambda \vert r' > r \}$, and $\#(X)$ the 
numnber of elements of $X$.

The opening transform \cite{Nacken:thesis} $\Omega_X$ of a binary image $X$ 
for a granulometry ${\alpha_r}$ is
\begin{equation}
  \Omega_X(x) = \max\{ r \in \Lambda \vert x \in \alpha_r(X) \}
\end{equation}

The pattern spectrum of a binary image $X$ using granulometry 
$\{\alpha_r\}$ is the histogram of $\Omega_X$ obtained with the same 
size distribution \cite{Nacken:thesis}, disregarding the bin for grey level 0.


\begin{figure}
\begin{center}
{\resizebox{\imsize}{!}{\includegraphics{blocks3}}}
{\resizebox{\imsize}{!}{\includegraphics{blocks3rec}}}
\end{center}
\caption{ \label{fig:opentransf} Opening transform with $\{\alpha_r\}$ as in 
 Fig. \ref{fig:blocks}: (left) original image; (right) opening transform
(contrast stretched for clarity). 
}
\end{figure}


\section{Spatial pattern spectra}
Pattern spectra only retain the amount of detail present at  scale $r$.
This can be amended by computing some parameterization of the spatial 
distribution in an image $\alpha_r(X) \setminus \alpha_{r+}(X)$ as a function of $r$. 

\begin{Def}
Let ${M}(X)$ be some parameterization of the spatial distribution of detail
in the image $X$. The spatial pattern spectrum ${S}_{{M},\alpha}$ is
then defined as
\begin{equation}
  ({S}_{{M},\alpha}(X))(r) = {M}(\alpha_r(X) \setminus \alpha_{r+}(X)).
\end{equation}  
\end{Def}

An obvious parameterization of the spatial distribution is through 
the use of moments. Focusing on the case of 2-D binary images, the 
moment $m_{ij}$ of order $ij$ of an image $X$ is given by
\begin{equation}
  m_{ij}(X) = \sum_{(x,y) \in \mathbf X} x^i y^j.
\end{equation}  
The spatial moment spectrum $S_{m_{ij},\alpha}$ of order $ij$ is
\begin{equation}
  (S_{m_{ij},\alpha}(X))(r) = m_{i,j}(\alpha_r(X) \setminus \alpha_{r^+}(X)).
\end{equation}  
For $i=0$ and $j=0$ we obtain the standard pattern spectrum. 
For each $r$, $(S_{m_{ij},\alpha}(X))(r)$ is just the moment of an image, 
therefore, derived parameters such as coordinates of the centre of mass, 
(co-)variances, skewness and kurtosis of the distribution of details at each
scale can be computed easily. We can then define pattern mean
spectra, pattern (co-)variance spectra, pattern kurtosis spectra, etc. The 
pattern mean-$x$ and variance-$x$ spectra 
($S_{\bar x,\alpha}$ and $S_{\sigma(x),\alpha}$) are defined as: 
\begin{align}
  S_{\bar x,\alpha} & = \frac{S_{m_{10},\alpha}} {S_{m_{00},\alpha}} \\
\intertext{and}
   S_{\sigma(x),\alpha} & = \sqrt{\frac{S_{m_{20},\alpha}}
                                 {S_{m_{00},\alpha}} 
                                 - S_{\bar x, \alpha}}.  
 \end{align}
These two are shown in Figures \ref{fig:tauspect} and \ref{fig:binspect}. Note that 
these definitions hold only where $(S_{m_{00},\alpha}(f))(r) \neq 0$. For all 
other values of $r$ they will be defined as zero. Further post-processing can
be done to compute central moments and moment invariant from pattern moment 
spectra \cite{Flusser:Suk:93,Hu:62}. 

\section{An Algorithm}

Nacken \cite{Nacken:thesis} derived an algorithm for computation
of pattern spectra for granulometries based on openings by discs of increasing
radius for various metrics, using the opening transform. After the
opening transform has been computed, it is straightforward to compute the 
pattern spectrum:
\begin{itemize}
\item Set all elements of array {\tt S} to zero
\item For all $x \in X$ increment {\tt S}[$\Omega_X(x)$] by one. 
\end{itemize}

To compute the pattern \emph{moment} spectrum, the only thing that needs to be
changed is the way {\tt S}[$\Omega_X(x)$] is incremented. As shown in Algorithm
\ref{alg:spect}.

\begin{algorithm}
\begin{itemize}
\item Set all elements of array {\tt S} to zero
\item For all $(x,y) \in X$ increment {\tt S}[$\Omega_X(x,y)$] by 
$x^iy^j$. 
\end{itemize}
\caption{ Algorithm for computation of pattern moment
spectrum of order $ij$. \label{alg:spect}}
\end{algorithm}

This algorithm can 
readily be adapted to other granulometries, simply by computing the 
appropriate opening transform.

\begin{figure}
\begin{center}
\begin{tabular}{c c}
{\resizebox{\imsize}{!}{\includegraphics{blocks3op}}} &
{\resizebox{\imsize}{!}{\includegraphics{blocksopen3a}}}\\
(a) & (b)\\
{\resizebox{\imsize}{!}{\includegraphics{blocksopen3vx}}}&
{\resizebox{\imsize}{!}{\includegraphics{blocksopen3vy}}}\\
(c) & (d) \\
\end{tabular}
\end{center}
\caption{ \label{fig:tauspect} 
The opening transform using city-block metric: (a) opening transform of
Fig. 1(c); (b) pattern spectrum; (c) pattern variance-$x$; 
(d) variance-$y$ spectra.}
\end{figure}



 


\renewcommand{\imsize}{0.3\columnwidth}
\begin{figure}
\begin{center}
{\resizebox{\imsize}{!}{\includegraphics{blocks1mx}}}
{\resizebox{\imsize}{!}{\includegraphics{blocks2mx}}}
{\resizebox{\imsize}{!}{\includegraphics{blocks3mx}}}\\
{\resizebox{\imsize}{!}{\includegraphics{blocks1vx}}}
{\resizebox{\imsize}{!}{\includegraphics{blocks1vx}}}
{\resizebox{\imsize}{!}{\includegraphics{blocks3vx}}}
\end{center}
\caption{ \label{fig:binspect} Pattern mean-$x$ (top) and variance-$x$ 
(bottom) spectra: the three collumns show spectra for Fig. 1(a), (b) and (c) 
from left to right respectively.  Unlike the standard pattern spectra, 
these spatial pattern spectra can distinguish the three images.}
\end{figure}

\section{Discussion}
Spatial pattern spectra form a useful supplement to ordinary pattern 
spectra, because of their ability to retain spatial information.  
Pattern moment spectra, in particular, are easily computed concurrently with 
computation of the standard pattern spectrum. Post-processing of these pattern
moment spectra can be done to yield a number of easily interpreted spectra, 
such as pattern mean, variance, skew, and kurtosis spectra, which have reduced 
covariance compared to the ``raw'' pattern moment spectra. Invariance to 
rotation, translation or scale change can also be achieved by post-processing
\cite{Flusser:Suk:93,Hu:62}.

In the future grey scale versions of these spatial pattern spectra will be 
developed. I expect that the efficient grey level algorithms for area and
attribute pattern spectra  
\cite{Meijster:Wilkinson:PAMI}
can be adapted to spatial pattern spectra as well.
 
%%% References

%% Note: use of BibTeX als works!!

\bibliographystyle{plain}
\begin{thebibliography}{1}

\bibitem{Flusser:Suk:93}
J.~Flusser and T.~Suk.
\newblock Pattern recognition by affine moment invariants.
\newblock {\em Pattern Recognition}, 26:167--174, 1993.

\bibitem{Hu:62}
M.~K. Hu.
\newblock Visual pattern recognition by moment invariants.
\newblock {\em IRE Transactions on Information Theory}, IT-8:179--187, 1962.

\bibitem{maragos89:_patter}
P.~Maragos.
\newblock Pattern spectrum and multiscale shape representation.
\newblock {\em IEEE Trans. Patt. Anal. Mach. Intell.}, 11:701--715, 1989.

\bibitem{Meijster:Wilkinson:PAMI}
A.~Meijster and M.~H.~F. Wilkinson.
\newblock A comparison of algorithms for connected set openings and closings.
\newblock {\em IEEE Trans. Patt. Anal. Mach. Intell.}, 24(4):484--494, 2002.

\bibitem{Nacken:thesis}
P.~F.~M. Nacken.
\newblock {\em Image Analysis Methods Based on Hierarchies of Graphs and
  Multi-Scale Mathematical Morphology}.
\newblock PhD thesis, University of Amsterdam, Amsterdam, The Netherlands,
  1994.

\end{thebibliography}

\end{multicols}

\end{document}

